/*
 *  Copyright (C) 2010 Matthias Buch-Kromann <mbk.isv@cbs.dk>
 * 
 *  This file is part of the IncrementalParser package.
 *  
 *  The IncrementalParser program is free software: you can redistribute it and/or modify
 *  it under the terms of the GNU Lesser General Public License as published by
 *  the Free Software Foundation, either version 3 of the License, or
 *  (at your option) any later version.
 * 
 *  This program is distributed in the hope that it will be useful,
 *  but WITHOUT ANY WARRANTY; without even the implied warranty of
 *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 *  GNU Lesser General Public License for more details.
 * 
 *  You should have received a copy of the GNU Lesser General Public License
 *  along with this program.  If not, see <http://www.gnu.org/licenses/>.
 */

package org.osdtsystem.incparser.parsers;

/**
 *
 * @author Matthias Buch-Kromann <mbk.isv@cbs.dk>
 */

/*public class IncrementalMSTParser extends AbstractParser {
    FeatureExtractor mpExtractor;
    int nodes;
    double[] nodescores = null;
    double[] scores = null;
    double[] scoresOptimal = null;;
    int[] heads = null;
    int lastnode = 0;

    public IncrementalMSTParser(Scorer scorer, FeatureExtractor mpExtractor, MSTParser baseParser) {
        this(scorer, mpExtractor, baseParser.unlabelledMstExtractor,
                baseParser.labelledMstExtractor, baseParser.labelAlphabet);
    }

    public IncrementalMSTParser(FeatureExtractor mpExtractor, MSTParser baseParser) {
        this(baseParser.scorer(), mpExtractor, baseParser);
    }

    public IncrementalMSTParser(Scorer scorer, FeatureExtractor mpExtractor,
            EdgeFactoredFeatureExtractor unlabelledMstExtractor,
            LabelledEdgeFactoredFeatureExtractor labelledMstExtractor,
            TwoWayFeatureHandler labelAlphabet) {
        super(scorer, unlabelledMstExtractor, labelledMstExtractor, labelAlphabet);
        this.mpExtractor = mpExtractor;
    }

    public FeatureVectorTrainingCache featureVectorTrainingCache(CONLLSentence sentence) {
        DefaultMstFeatureVectorTrainingCache featureVectorCache
                = new DefaultMstFeatureVectorTrainingCache(sentence, unlabelledMstExtractor,
                    labelledMstExtractor, labelAlphabet);
        return(featureVectorCache);
    }

    int entry(int head, int node) {
        return head * nodes + node;
    }

    boolean dominates(int dominator, int node) {
        return dominates(dominator, node, 0);
    }

    boolean dominates(int dominator, int node, int height) {
        if (node == 0)
            return false;
        if (height > heads.length)
            return false; // Trapped in a cycle
        if (node == dominator)
            return height > 0;
        return dominates(dominator, heads[node], height + 1);
    }

    void attachToBestLeft(int node) {
        //  Find best head to the left
        double bestscore = Double.NEGATIVE_INFINITY;
        int besthead = 0;
        for (int head = 0; head < node; ++head) {
            double score = scores[entry(head, node)];
            if (score > bestscore) {
                bestscore = score;
                besthead = head;
            }
        }
        heads[node] = besthead;
        nodescores[node] = bestscore;
    }

    void tryAttachToRight(int node, int head) {
        // Try to make an attachment to the two nodes directly
        if (node == head) {
            return;
        } else if (! dominates(node, head)) {
            heads[node] = head;
            nodescores[node] = scores[entry(head, node)];
        } else {
            // Oops! node dominates head so direct attachment would result in a cycle.
            // Try to see if we can reattach any of the nodes from head and up to
            // (and excluding) node to a head that isn't dominated by node,
            // at a lower cost than the potential gain from reattaching node
            // to head
            double gainOnNode = scores[entry(head, node)] - nodescores[node];
            if (gainOnNode <= 0)
                return;
            int repaired = head;
            int bestRepaired = -1;
            int bestRepairedHead = -1;
            double bestGain = 0;
            while (repaired != node && repaired != 0) {
                // Calculate the price of reattaching repaired somewhere that isn't dominated
                // by node
                for (int repairedHead = lastnode; repairedHead >= 0; --repairedHead) {
                    // How much do we lose on repaired by doing the repair?
                    double costOnRepaired = scores[entry(repairedHead, repaired)] - nodescores[repaired];

                    // Save the repair if we gain by doing it
                    if ((costOnRepaired + gainOnNode > bestGain )
                            && (node != repairedHead) && (! dominates(node, repairedHead))) {
                        bestGain = costOnRepaired + gainOnNode;
                        bestRepaired = repaired;
                        bestRepairedHead = repairedHead;
                    }
                }

                // Move up to the next node
                repaired = heads[repaired];
            }

            // Now perform the best repair that we could find
            if (bestGain > 0) {
                // Yes! We could repair node by also repairing repair
                heads[node] = head;
                heads[bestRepaired] = bestRepairedHead;
                nodescores[node] = scores[entry(head, node)];
                nodescores[bestRepaired] = scores[entry(bestRepairedHead, bestRepaired)];
            }
        }
    }

    public LabelledHeadsWithFeaturevectors trainParse(CONLLSentence sentence,
            WeightVector weightVector, FeatureVectorTrainingCache cache) {
        // Compute pairwise scores
        nodes = sentence.size();
        scores = new double[nodes * nodes];
        scoresOptimal = new double[nodes];
        for (int node = 0; node < nodes; node++) {
            scoresOptimal[node] = Double.NEGATIVE_INFINITY;
            for (int head = 0; head < nodes; head++) {
                double score = (head == node)
                        ? Double.NEGATIVE_INFINITY
                        : scorer.getScore(weightVector,
                            cache.unlabelledFeatures(head, node));
                scores[entry(head, node)] = score;
                if (scoresOptimal[node] < score)
                    scoresOptimal[
                            node] = score;
            }
        }

        // Process nodes incrementally from left to right
        heads = new int[nodes];
        nodescores = new double[nodes];
        Arrays.fill(heads, 0);
        for (int node = 1; node < nodes; node++) {
            lastnode = node;

            // First attach to the best possible left head
            attachToBestLeft(node);

            // Now try to see if any of the nodes to the left want to attach to the right
            for (int dependent = node - 1; dependent > 0; --dependent) {
                if (nodescores[dependent] < scores[entry(node, dependent)]) {
                    // Attachment to new node would be better: try to repair the
                    // old attachment
                    tryAttachToRight(dependent, node);
                }
            }
        }

        // Labels
        String[] labels = new String[nodes];
        for (int node = 0; node < heads.length; ++node) {
            labels[node] = String.format("%6g", nodescores[node]);
        }

        // Compute feature vectors
        List<FeatureVector> featureVectors = new ArrayList<FeatureVector>();
        for (int i = 1; i < heads.length; ++i)
            featureVectors.add(cache.unlabelledFeatures(heads[i], i));

        // Log output
        //Log.fine("Parsed \"" + sentence.toTokenString() + "\" as "
        //        + parse.stringFinal());
        return new DefaultLabelledHeadsWithFeaturevectors(asList(heads),
                Arrays.asList(labels), featureVectors);
    }

    static List<Integer> asList(int[] array) {
        Integer[] list = new Integer[array.length];
        for (int i = 0; i < array.length; ++i)
            list[i] = array[i];
        return Arrays.asList(list);
    }

    static String arrayToString(double[] array) {
        return(new DefaultDenseDoubleMatrix2D(array, 1, array.length).toString());
    }

}*/
